#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAXSIZE 100

typedef int Item;

typedef struct {
  int length;
  Item item[];
} Node, *List;

Item temp[MAXSIZE];

void empty(void);
List init(void);
void showArr(const Item arr[], int length);
void showList(const List list);
void showBySelectSorted(const List list);
void showByInsertSorted(const List list);
void showBySwapSorted(const List list);
void findItem(const List list);
void findBySorted(const List list);

int main(void) {
  int choose;
  List list = init();
  puts("当前线性表数据如下:");
  showList(list);
  while (!(choose = 0)) {
    puts("请选择以下操作执行:");
    puts("1.查看原数据");
    puts("2.显示选择排序结果");
    puts("3.显示插入排序结果");
    puts("4.显示交换排序结果");
    puts("5.排序前顺序查找比较");
    puts("6.排序后二分查找比较");
    puts("7.退出");
    printf("选择指令:");
    scanf("%d", &choose);
    empty();
    switch (choose) {
    case 1:
      showList(list);
      break;
    case 2:
      showBySelectSorted(list);
      break;
    case 3:
      showByInsertSorted(list);
      break;
    case 4:
      showBySwapSorted(list);
      break;
    case 5:
      findItem(list);
      break;
    case 6:
      findBySorted(list);
      break;
    case 7:
      exit(0);
      break;
    default:
      puts("请输入正确的指令");
    }
  }
  return false;
}

void empty() {
  while (getchar() != '\n') {
    continue;
  }
}

List init() {
  int i;
  List list = malloc(sizeof(Node) + MAXSIZE * sizeof(Item));
  printf("请输入数组的初始化长度(100以内的整数):");
  scanf("%d", &list->length);
  empty();
  srand((unsigned)time(0));
  for (i = 0; i < list->length; i++) {
    list->item[i] = rand() % 100;
  }
  return list;
}

void showArr(const Item arr[], int length) {
  int i = 0;
  while (i++ < length) {
    printf("%2d\t", arr[i - 1]);
    if (!((i) % 5)) {
      puts("");
    }
  }
  puts("");
}

void showList(const List list) {
  int i;
  for (i = 0; i < list->length; i++) {
    printf("%2d\t", list->item[i]);
    if (!((i + 1) % 5)) {
      puts("");
    }
  }
  puts("");
}

void showBySelectSorted(const List list) {
  int index, current, minIndex, compareCount, moveCount;
  Item swap;
  compareCount = 0;
  moveCount = 0;
  memcpy(temp, list->item, sizeof(Item) * MAXSIZE);
  for (index = 0; index < list->length - 1; index++) {
    minIndex = index;
    for (current = index + 1; current < list->length; current++) {
      compareCount++;
      if (temp[current] < temp[minIndex]) {
        minIndex = current;
      }
    }
    swap = temp[index];
    temp[index] = temp[minIndex];
    temp[minIndex] = swap;
    moveCount++;
  }
  printf("比较%d次,移动%d次\n", compareCount, moveCount);
  showArr(temp, list->length);
}

void showByInsertSorted(const List list) {
  Item current, compareCount, moveCount;
  int index, preIndex;
  compareCount = 0;
  moveCount = 0;
  memcpy(temp, list->item, sizeof(Item) * MAXSIZE);
  for (index = 1; index < list->length; index++) {
    preIndex = index - 1;
    current = temp[index];
    while (preIndex >= 0 && temp[preIndex] > current) {
      compareCount++;
      temp[preIndex + 1] = temp[preIndex];
      preIndex--;
    }
    compareCount++;
    if (temp[preIndex + 1] != current) {
      temp[preIndex + 1] = current;
      moveCount++;
    }
  }
  printf("比较%d次,移动%d次\n", compareCount, moveCount);
  showArr(temp, list->length);
}

void showBySwapSorted(const List list) {
  int out, in, compareCount, moveCount;
  Item swap;
  memcpy(temp, list->item, sizeof(Item) * MAXSIZE);
  compareCount = 0;
  moveCount = 0;
  for (out = 0; out < list->length - 1; out++) {
    for (in = 0; in < list->length - 1 - out; in++) {
      if (temp[in] > temp[in + 1]) {
        swap = temp[in + 1];
        temp[in + 1] = temp[in];
        temp[in] = swap;
        moveCount++;
      }
      compareCount++;
    }
  }
  printf("比较%d次,移动%d次\n", compareCount, moveCount);
  showArr(temp, list->length);
}

void findItem(const List list) {
  int index, compareCount, search;
  compareCount = 0;
  printf("输入查找的数值:");
  scanf("%d", &search);
  empty();
  for (index = 0; index < list->length; index++) {
    if (list->item[index] == search) {
      compareCount++;
      break;
    }
    compareCount++;
  }
  printf("查找的是第%d个数,共比较%d次\n", index + 1, compareCount);
}

void findBySorted(const List list) {
  int start, middle, end, compareCount, search;
  compareCount = 0;
  start = 0;
  end = list->length - 1;
  puts("进行数组排列");
  showByInsertSorted(list);
  printf("输入查找的数值:");
  scanf("%d", &search);
  empty();
  while (start <= end) {
    middle = (start + end) / 2;
    if (temp[middle] == search) {
      compareCount++;
      printf("排序后第%d个数,比较%d次\n", middle + 1, compareCount);
      return;
    } else if (search < temp[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    compareCount++;
  }
  printf("比较%d次,没有找到该数\n", compareCount);
}
